package com.gitee.swsk33.algorithms.string;

/**
 * 自己实现的字符串匹配算法
 */
public class StringMatch {

	/**
	 * 暴力匹配子串在主串的位置
	 *
	 * @param main 主串
	 * @param sub  子串
	 * @return 子串在主串中首次出现的位置，若匹配失败返回-1
	 */
	public static int violentMatchIndexOf(String main, String sub) {
		int i = 0;
		int j = 0;
		while (i < main.length() && j < sub.length()) {
			// 开始遍历每一个字符进行比较
			// 若当前字符相等，则i，j后移一位继续比较
			if (main.charAt(i) == sub.charAt(j)) {
				i++;
				j++;
			} else {
				// 否则，i回退到i这一趟最开始匹配时的后一位，j回退到0
				i = i - j + 1;
				j = 0;
			}
		}
		// 比较完毕，如果说j现在大于子串的长度 - 1（正常情况下匹配完成后j=sub的最后一个字符的索引+1，恰好等于sub长度值，因为字符串第一个字符索引是0），说明子串全部匹配完成，匹配成功
		if (j > sub.length() - 1) {
			return i - sub.length();
		} else {
			// 否则说明匹配失败
			return -1;
		}
	}

	/**
	 * KMP算法-根据模式串求得next数组
	 *
	 * @param sub 模式串
	 * @return 其对应的next数组
	 */
	private static int[] getNext(String sub) {
		int[] next = new int[sub.length()];
		// 初始化
		next[0] = -1;
		next[1] = 0;
		int m = 0;
		int n = 1;
		// 开始判断sub[m]和sub[n]的情况
		while (n < sub.length() - 1) {
			// 如果相等或者不相等但是m == -1时（无法再次级比较时）
			if (m == -1 || sub.charAt(m) == sub.charAt(n)) {
				m++;
				n++;
				next[n] = m;
			} else {
				// 不相等，次级比较
				m = next[m];
			}
		}
		return next;
	}

	/**
	 * KMP算法-求next数组修正后的数组nextval
	 *
	 * @param sub 模式串
	 * @return 其对应的nextval数组
	 */
	public static int[] getNextVal(String sub) {
		int[] nextval = new int[sub.length()];
		nextval[0] = -1;
		int m = 0;
		int n = 1;
		while (n < sub.length() - 1) {
			if (m == -1 || sub.charAt(m) == sub.charAt(n)) {
				m++;
				n++;
				// 进一步判断m，n自加之后是否相等
				if (sub.charAt(m) != sub.charAt(n)) {
					nextval[n] = m;
				} else {
					nextval[n] = nextval[m];
				}
			} else {
				m = nextval[m];
			}
		}
		return nextval;
	}

	/**
	 * KMP算法-匹配子串在主串的位置
	 *
	 * @param main 主串
	 * @param sub  子串
	 * @return 子串在主串第一次出现的位置，若匹配失败返回-1
	 */
	public static int KMPMatchIndexOf(String main, String sub) {
		// 先根据模式串求得next数组
		int[] next = getNext(sub);
		int i = 0;
		int j = 0;
		// 开始逐个比较
		while (i < main.length() && j < sub.length()) {
			// 如果当前比较的字符相等，则i，j后移一位比较下一个
			// 如果j被重定向至-1，说明模式串第一位就失配了，这时也只能把i，j后移一位才能继续比较
			if (j == -1 || main.charAt(i) == sub.charAt(j)) {
				i++;
				j++;
			} else {
				// 不相等，则重定向至next[j]
				j = next[j];
			}
		}
		// 比较完毕，如果说j现在大于子串的长度 - 1（正常情况下匹配完成后j=sub的最后一个字符的索引+1，恰好等于sub长度值，因为字符串第一个字符索引是0），说明子串全部匹配完成，匹配成功
		if (j > sub.length() - 1) {
			return i - sub.length();
		} else {
			// 否则说明匹配失败
			return -1;
		}
	}

}